#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        set<pair<int,int>> S;
        int result = 0;
        for(int i = 0;i<grid.size();++i){
            for(int j=0;j<grid[0].size();++j){
                if(grid[i][j]=='1'&&S.find(make_pair(i,j))==S.end()){
                    // S.insert(make_pair(i,j));
                    ++result;
                    DFS(grid,i,j,S);
                }
            }
        }
        return result;
    }
    void DFS(vector<vector<char>>& grid,int i,int j,set<pair<int,int>>& S){
        if(i<0||i>=grid.size()||j<0||j>=grid[0].size()||grid[i][j]=='0'||S.find(make_pair(i,j))!=S.end()){
            return ;
        }
        S.insert(make_pair(i,j));
        DFS(grid,i-1,j,S);
        DFS(grid,i+1,j,S);
        DFS(grid,i,j-1,S);
        DFS(grid,i,j+1,S);
    }
};

int main(){
    vector<vector<char>> V={{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
    Solution S;
    cout<<S.numIslands(V)<<endl;
}